package DynamicProgramingSeries;

public class MaxProduct_152 {
    public int maxProduct(int[] nums) {
        int length = nums.length;
        // 记录最大值和最小值，因为负负得正，当前数如果是负数，有可能和min相乘变成最大值
        long[] dpMax = new long[length];
        long[] dpMin = new long[length];

        for (int i = 0; i < length; i++) {
            dpMax[i] = nums[i];
            dpMin[i] = nums[i];
        }

        for (int i = 1; i < length; i++) {
            dpMax[i] = Math.max(dpMax[i - 1] * nums[i], Math.max(nums[i], dpMin[i - 1] * nums[i]));
            dpMin[i] = Math.min(dpMin[i - 1] * nums[i], Math.min(nums[i], dpMax[i - 1] * nums[i]));
            if (dpMin[i] < Integer.MIN_VALUE) {
                dpMin[i] = nums[i];
            }
        }

        int result = (int) dpMax[0];
        for (int i = 1; i < length; i++) {
            result = Math.max(result, (int) dpMax[i]);
        }
        return result;
    }
}
